//
// Created by user on 2022/3/2.
//
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

bool compare(int a, int b){
    return a>b;
}
int lastStoneWeight1(vector<int>& stones) {
    int n = stones.size();
    for (int i = 0; i < stones.size()-1; ++i) {
        sort(stones.begin(), stones.end());
        int y = stones[n-1];
        int x = stones[n-2];
        if(x==0){break;}
        stones[n-1] = y-x;
        stones[n-2] = 0;
    }
    return stones[n-1];
}

//大顶堆 p
int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> pq;//大顶堆
    //priority_queue<int, vector<int>, greater<int>>a; //小顶堆
    int n = stones.size();
    for (int i = 0; i <n ; ++i) {
        pq.push(stones[i]);
    }
    while (pq.size()>1){
        int y = pq.top();
        pq.pop();
        int x = pq.top();
        pq.pop();
        pq.push(y-x);
    }

    return pq.top();
}